package com.company;


public class Main {
    private static void swap(int a[], int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static void sort(int a[]) {
        int len = a.length;

        for (int end = len - 1; end > 0; end--) {
            for (int begin = 0; begin <= (end - 1) / 2; begin++) {
                int max = begin;
                if (begin * 2 + 1 <= end && a[begin * 2 + 1] > a[max]) {
                    max = begin * 2 + 1;
                }
                if (begin * 2 + 2 <= end && a[begin * 2 + 2] > a[max]) {
                    max = begin * 2 + 2;
                }

                if (max != begin) {
                    swap(a, max, begin);

                    for (int i = begin; i > 0 && a[i] > a[(i - 1) / 2]; i = (i - 1) / 2) {
                        swap(a, i, (i - 1) / 2);
                    }
                }
            }

            swap(a, 0, end);
        }
    }

    public static void main(String[] args) {
        int N = 20;
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = (int) (Math.random() * N * 10);
        }

        for (int i = 0; i < N; i++) {
            System.out.print(a[i] + "\t");
        }
        System.out.println();

        sort(a);

        for (int i = 0; i < N; i++) {
            System.out.print(a[i] + "\t");
        }
        System.out.println();
    }
}